package cn.edu.njust.alg.leetcode;

public class Leetcode_55_Jump_Game {

	public static boolean canJump(int[] nums) {
		if (nums.length <= 1) {
			return true;
		}
		int n = nums.length;
		int maxstep = nums[0];
		for (int i = 1; i < n; i++) {
			if (maxstep == 0)
				return false;
			maxstep--;
			if (maxstep < nums[i]) {
				maxstep = nums[i];
			}
			if (maxstep + i >= n - 1) {
				return true;
			}
		}
		return true;
	}

	public static void main(String[] args) {

		int[] nums = { 2, 3, 1, 1, 4 };

		System.out.println(canJump(nums));
	}

}
